package mysgoog.bot.algo;

import java.util.*;

import mysgoog.board.*;
import mysgoog.bot.*;
import mysgoog.gtp.*;
import mysgoog.util.*;

/**
 * 
 * @author Wang Xin'an
 */
public class AlphaBetaSearch {
	private static final int depth = 4;
	private static final Board dumbBrd = Config.getEmptyBoard();
	private static final int MAX_SIZE = dumbBrd.BOARD_ELEMNUM;
	static public final int[] deltai = { -1, 1, 0, 0 };
	static public final int[] deltaj = { 0, 0, -1, 1 };
	/*
	 * if moves[] is null , means we only want to know if it can be captured.
	 * only require that origin keep updating its stones info
	 */
	private static Color[] board = new Color[MAX_SIZE];
	// ========
	private static int[][] libs = new int[MAX_SIZE][MAX_SIZE];
	private static int[] libn = new int[MAX_SIZE]; // if libn[k]> depth,
	// just record depth
	// don't record it in
	// libs(it's useless)
	private static int[] next_stone = new int[MAX_SIZE];
	// private static boolean[] accessed = new boolean[MAX_SIZE];
	// used in completeSet() record all the added liberties
	private static boolean[] complete = new boolean[MAX_SIZE];
	// used in DFS() to build libn ,libs
	private static boolean[] dfs = new boolean[MAX_SIZE]; // connected
	// stone
	private static boolean[] dfs_lib = new boolean[MAX_SIZE]; // liberties
	private static int[] queue = new int[MAX_SIZE];
	private static int[] queue2 = new int[MAX_SIZE];
	private static boolean[][] capture_innerAccess = new boolean[(depth + 1)
			* (depth + 1)][MAX_SIZE];
	private static boolean[][] defend_innerAccess = new boolean[(depth + 1)
			* (depth + 1)][MAX_SIZE];
	// copy of current state
	private static Color[][] board_copy = new Color[depth * 8][MAX_SIZE];
	private static int[][][] libs_copy = new int[depth * 8][MAX_SIZE][MAX_SIZE];
	private static int[][] libn_copy = new int[depth * 8][MAX_SIZE];
	private static int[][] next_copy = new int[depth * 8][MAX_SIZE];

	private static boolean[] getArrayCapture(int n, int steps) {
		Lib.assertTrue(n <= depth);
		return capture_innerAccess[n * (depth + 1) + steps];
	}

	private static boolean[] getArrayDefend(int n, int steps) {
		Lib.assertTrue(n <= depth);
		return defend_innerAccess[n * (depth + 1) + steps];
	}

	private static final int NONEED_DEFEND = -1; // too many liberties

	static public int Capture(Board board, int pos, int[] moves) {
		initial(board);
		return Capture(pos, moves, null, depth, 0);

	}

	/*
	 * return -1 if there's no need to defend
	 */
	static public int Defend(Board board, int pos, int[] moves) {
		initial(board);
		if (libn[pos] > depth)
			return NONEED_DEFEND;
		return Defend(pos, moves, null, depth-1, 0);
	}

	static private int Capture1(int pos, int[] moves, boolean[] accessed,
			int steps) {
		int n = libn[pos];
		Lib.assertTrue(n == 1 && steps > 0);
		if (accessed != null)
			accessed[libs[pos][0]] = true;
		if (moves != null)
			moves[0] = libs[pos][0];
		return 1;
	}

	static private int[] defend1Arr = new int[MAX_SIZE];

	/*
	 * static private int Defend1(int pos, int[] moves, boolean[] accessed, int
	 * steps, int level) { snapshot(level);
	 * 
	 * int n = libn[pos]; int lib = libs[pos][0]; // will be use inside the
	 * function Lib.assertTrue(n == 1 && steps > 0); if (accessed != null)
	 * accessed[lib] = true; int resn = 0; Color opp_color =
	 * board[pos].complement(); addMove(lib, board[pos]); if (libn[pos] > 1) {
	 * if (moves != null) moves[resn] = lib; ++resn; } // undoMove(lib);
	 * recover(level);
	 * 
	 * int next = pos; do { int i = dumbBrd.posX(next); int j =
	 * dumbBrd.posY(next); for (int k = 0; k < 4; ++k) { int ai = i + deltai[k];
	 * int aj = j + deltaj[k]; int apos = dumbBrd.makePos(ai, aj); if
	 * (dumbBrd.inBoard(dumbBrd.makePos(ai, aj)) && board[apos] == opp_color &&
	 * libn[apos] == 1) { if (accessed != null) accessed[libs[apos][0]] = true;
	 * if (moves != null) { int k2 = 0; for (; k2 < resn; ++k2) { if
	 * (libs[apos][0] == moves[k2]) break; } if (k2 == resn) { moves[resn++] =
	 * libs[apos][0]; } } else resn = 1; } } next = next_stone[next]; } while
	 * (next != pos); // Lib.log("end8"); return resn; }
	 */
	static private int Capture(int pos, int[] moves, boolean[] accessed,
			int steps, int level) {
		snapshot(level);
		// System.out.println("Capture :<"+dumbBrd.posX(pos)+","+dumbBrd.posY(pos)+">");
		int n = libn[pos];
		Lib.log("Capture beg MAX_SIZE" + n + "," + steps);
		if (n > steps)
			return 0;
		if (n == 1)
			return Capture1(pos, moves, accessed, steps);
		int resn = 0;
		if (n == 2) {
			// seem to be the best way to go
			resn = captureLadder(pos, moves, level + 1);
			if (resn > 0) {
				return resn;
			}
			// System.out.println("Capture3 :"+libn[pos]);
			// Lib.log("capture line beg");
			resn = captureLine(pos, moves, level + 1);
			// Lib.log("capture line end:" + resn);
			if (resn > 0)
				return resn;
		}
		// System.out.println("Capture2 :"+libn[pos]);
		Color my_color = board[pos].complement();
		int[] tmplibs = new int[n];
		System.arraycopy(libs[pos], 0, tmplibs, 0, n);
		Lib.log("Capture beg 2 (" + n + ")");
		if (steps == n) {
			Lib.log("Capture beg 3+" + n);
			for (int k = 0; k < n; ++k) {
				addMove(tmplibs[k], my_color);
				if (accessed != null) {
					Lib.log("Capture beg 3 +" + tmplibs[k]);
					accessed[tmplibs[k]] = true;
				}
				// not suicide
				if (libn[tmplibs[k]] > 0) {
					if (Defend(pos, null, accessed, steps - 1, level + 1) == 0) {
						Lib.log("Capture beg 5");
						if (moves != null) {
							int k2 = 0;
							for (; k2 < resn; ++k2) {
								if (moves[k2] == tmplibs[k])
									break;
							}
							if (k2 == resn)
								moves[resn++] = tmplibs[k];
						} else
							resn = 1;
					}
				}
				// undoMove(tmplibs[k]);
				recover(level);
			}
		} else {
			boolean[] innerAccessed = getArrayCapture(n, steps);
			Arrays.fill(innerAccessed, 0, MAX_SIZE, false);
			Lib.log("Capture beg 4");
			// step 1

			Defend(pos, null, innerAccessed, steps - 1, level + 1); // n!=1

			for (int k = 0; k < n; ++k)
				innerAccessed[libs[pos][k]] = true;
			// step 2
			completeSet(innerAccessed, steps);
			// step 3
			for (int k = 0; k < MAX_SIZE; ++k) {
				if (innerAccessed[k] && board[k] == Color.EMPTY) {
					if (accessed != null)
						accessed[k] = true;
					addMove(k, my_color);
					// not suicide
					if (libn[k] > 0) {
						if (Defend(pos, null, accessed, steps - 1, level + 1) == 0) {
							if (moves != null) {
								int k2 = 0;
								for (; k2 < resn; ++k2) {
									if (moves[k2] == k)
										break;
								}
								if (k2 == resn)
									moves[resn++] = k;
							} else
								resn = 1;
						}
					}
					// undoMove(k);
					recover(level);
					// Lib.log("end6");
				}
			}
		}
		return resn;
	}

	static private int Defend(int pos, int[] moves, boolean[] accessed,
			int steps, int level) {
		// System.out.println("Defend :<"+dumbBrd.posX(pos)+","+dumbBrd.posY(pos)+">");
		snapshot(level);
		int n = libn[pos];
		// Lib.log("beg defend MAX_SIZE(" + n + ")");
		Lib.assertTrue(n > 0);
		if (n > steps) {
			if (accessed != null) {
				for (int k = 0; k < n; ++k)
					accessed[libs[pos][k]] = true;
			}
			return NONEED_DEFEND;
		}
		Color my_color = board[pos];
		int resn = 0;
		if (n == 1) {
			if (accessed != null) {
				accessed[libs[pos][0]] = true;
			}
			addMove(libs[pos][0], my_color);
			// suicide
			if (libn[pos] == 0) {
				recover(level);
				return 0;
			} else {
				int tmpres = Capture(pos, null, accessed, steps, level + 1);
				if (tmpres == 0) {
					recover(level);
					if (moves != null) {
						moves[0] = libs[pos][0];
					}
					return 1;
				} else {
					recover(level);
					return 0;
				}
			}
		}
		boolean[] innerAccessed = getArrayDefend(n, steps);
		Arrays.fill(innerAccessed, false);
		for (int k = 0; k < n; ++k)
			innerAccessed[libs[pos][k]] = true;
		// step 1
		Capture(pos, moves, innerAccessed, steps - 1, level + 1);

		// step2
		completeSet(innerAccessed, steps);
		// step 3
		// Lib.log("beg defend 2");
		int counter = 0;
		for (int k = 0; k < innerAccessed.length; ++k) {
			if (innerAccessed[k] && board[k] == Color.EMPTY) {
				++counter;
				if (accessed != null)
					accessed[k] = true;
				addMove(k, my_color);
				// not suicide
				if (libn[k] > 0) {
					// Lib.log("beg defend 3");
					if (Capture(pos, null, accessed, steps, level + 1) == 0) {
						// Lib.log("beg defend 4");
						if (moves != null) {
							int k2 = 0;
							for (; k2 < resn; ++k2) {
								if (moves[k2] == k)
									break;
							}
							if (k2 == resn)
								moves[resn++] = k;
						} else
							resn = 1;
					}
				}
				// undoMove(k);
				recover(level);
			}
		}
		// Lib.log("end7 +" + counter);
		return resn;
	}

	static private int captureLine(int pos, int[] moves, int level) {
		snapshot(level);
		int n = libn[pos];
		if (n != 2)
			return 0;
		int lib1 = libs[pos][0];
		int lib2 = libs[pos][1];
		int direction = direction(lib1, lib2);
		Lib.log("direction: " + direction);
		if (direction < 0)
			return 0;
		int res = 0;
		if (line(direction, pos, level + 1)) {
			if (moves != null)
				moves[res++] = lib1;
			else {
				recover(level);
				return 1;
			}
		}
		recover(level);
		if (line(direction(lib2, lib1), pos, level + 1)) {
			if (moves != null)
				moves[res++] = lib2;
			else {
				recover(level);
				return 1;
			}
		}
		recover(level);
		return res;
	}

	static private int[] lineArr = new int[MAX_SIZE];

	// don't need to recover
	static private boolean line(int direction, int pos, int level) {
		int n = libn[pos];
		if (n != 2)
			return false;
		Color opp_color = board[pos];
		Color mycolor = opp_color.complement();
		int lib1 = libs[pos][0];
		int lib2 = libs[pos][1];
		// maybe opposite
		if (direction(lib1, lib2) != direction) {
			lib1 = libs[pos][1];
			lib2 = libs[pos][0];
		}
		// not parallel
		if (direction(lib1, lib2) != direction)
			return false;
		addMove(lib1, mycolor);
		if (libn[lib1] <= 0) {
			// undoMove(lib1);
			return false;
		}
		int def1 = Defend(pos, lineArr, null, 1, level); // this level don't
		// need "level"
		if (def1 == 0) {
			// undoMove(lib1);
			return true;
		} else if (def1 == NONEED_DEFEND || def1 > 1) {
			// undoMove(lib1);
			return false;
		} else if (lineArr[0] == lib2) {
			// only one lib
			addMove(lib2, opp_color);
			boolean b = line(direction, pos, level);
			// undoMove(lib2);
			// undoMove(lib1);
			return b;
		} else {
			// undoMove(lib1);
			return false;
		}
	}

	/*
	 * capture worm(with 2 liberties) (steps>=2) don't add all the stones in
	 * access , since they are too much check if the worm can be captured by
	 * ladder
	 */
	static private int captureLadder(int pos, int[] moves, int level) {
		snapshot(level);
		Lib.log("Ladder beg");
		int n = libn[pos];
		if (n != 2) {
			return 0;
		}
		int lib1 = libs[pos][0];
		int lib2 = libs[pos][1];
		int direction = diagonal(lib1, lib2);
		if (direction < 0)
			return 0;
		int res = 0;
		if (ladder(direction, pos, level + 1)) {
			if (moves != null)
				moves[res++] = lib1;
			else {
				recover(level);
				return 1;
			}
		}
		recover(level);
		if (ladder(diagonal(lib2, lib1), pos, level + 1)) {
			if (moves != null)
				moves[res++] = lib2;
			else {
				recover(level);
				return 1;
			}
		}
		recover(level);
		return res;
	}

	static private int[] ladderArr = new int[MAX_SIZE];

	static private boolean ladder(int direction, int pos, int level) {
		int n = libn[pos];
		if (n != 2)
			return false;
		Color opp_color = board[pos];
		Color mycolor = opp_color.complement();
		int lib1 = libs[pos][0];
		int lib2 = libs[pos][1];
		// maybe opposite
		if (diagonal(lib1, lib2) != direction) {
			lib1 = libs[pos][1];
			lib2 = libs[pos][0];
		}
		// not parallel
		if (diagonal(lib1, lib2) != direction)
			return false;
		addMove(lib1, mycolor);
		if (libn[lib1] <= 0) {
			// undoMove(lib1);
			return false;
		}
		int def1 = Defend(pos, ladderArr, null, 1, level);
		if (def1 == 0) {
			// undoMove(lib1);
			return true;
		} else if (def1 == NONEED_DEFEND || def1 > 1) {
			// undoMove(lib1);
			return false;
		} else if (ladderArr[0] == lib2) {
			// only one lib
			addMove(lib2, opp_color);
			boolean b = ladder(diagonal(lib2, lib1), pos, level);
			// undoMove(lib2);
			// undoMove(lib1);
			return b;
		} else {
			// undoMove(lib1);
			return false;
		}
	}

	static private int[] digI = { 1, -1, 1, -1 };
	static private int[] digJ = { 1, 1, -1, -1 };

	static private int diagonal(int pos1, int pos2) {
		for (int k = 0; k < 4; ++k) {
			if (dumbBrd.makePos(dumbBrd.posX(pos1) + digI[k], dumbBrd
					.posY(pos1)
					+ digJ[k]) == pos2)
				return k;
		}
		return -1;
	}

	static private int[] dirI = { 1, 1, 1, -1, -1, -1, 0, 0 };
	static private int[] dirJ = { 1, -1, 0, 1, -1, 0, 1, -1 };

	static private int direction(int pos1, int pos2) {
		Lib.log("<" + dumbBrd.posX(pos1) + "," + dumbBrd.posY(pos1) + ">");
		Lib.log("<" + dumbBrd.posX(pos2) + "," + dumbBrd.posY(pos2) + ">");
		for (int k = 0; k < 8; ++k) {
			if (dumbBrd.makePos(dumbBrd.posX(pos1) + dirI[k], dumbBrd
					.posY(pos1)
					+ dirJ[k]) == pos2)
				return k;
		}
		return -1;
	}

	/*
	 * add all potential points for accessed
	 */
	static private void completeSet(boolean[] accessed, int maxlibn) {
		Arrays.fill(complete, 0, MAX_SIZE, false);
		for (int k = 0; k < accessed.length; ++k) {
			if (accessed[k]) {
				for (int k1 = 0; k1 < 4; ++k1) {
					int ai = dumbBrd.posX(k) + deltai[k1];
					int aj = dumbBrd.posY(k) + deltaj[k1];
					int apos = dumbBrd.makePos(ai, aj);
					if (dumbBrd.inBoard(dumbBrd.makePos(ai, aj))
							&& board[apos] != Color.EMPTY
							&& libn[apos] <= maxlibn) {
						for (int k2 = 0; k2 < libn[apos]; ++k2) {
							complete[libs[apos][k2]] = true;
						}
					} else if (dumbBrd.inBoard(dumbBrd.makePos(ai, aj))
							&& board[apos] == Color.EMPTY) {
						complete[apos] = true;
					}
				}
			}
		}
		for (int k = 0; k < MAX_SIZE; ++k)
			if (complete[k])
				accessed[k] = true;
	}

	/*
	 * update libs[],libn[],board[], next_stone[]
	 */
	static private boolean[] needReBFS = new boolean[MAX_SIZE];

	static private void addMove(int pos, Color color) {
		Lib.assertTrue(board[pos] == Color.EMPTY);
		Arrays.fill(needReBFS, false);
		Color opp = color.complement();
		for (int k = 0; k < 4; ++k) {
			int ai = dumbBrd.posX(pos) + deltai[k];
			int aj = dumbBrd.posY(pos) + deltaj[k];
			int apos = dumbBrd.makePos(ai, aj);
			if (dumbBrd.inBoard(dumbBrd.makePos(ai, aj)) && !needReBFS[apos]
					&& board[apos] == opp) {
				if (libn[apos] == 1) {
					Lib.assertTrue(libs[apos][0] == pos);
					// System.out.println("end");
					libn[apos] = 0;
					int next = apos;
					do {
						board[next] = Color.EMPTY;
						for (int k2 = 0; k2 < 4; ++k2) {
							int a2i = dumbBrd.posX(next) + deltai[k2];
							int a2j = dumbBrd.posY(next) + deltaj[k2];
							int a2pos = dumbBrd.makePos(a2i, a2j);
							if (dumbBrd.inBoard(a2pos) && board[a2pos] == color) {
								needReBFS[a2pos] = true;
							}
						}
						next = next_stone[next];
					} while (apos != next);
				} else {
					needReBFS[apos] = true;
				}
			}
		}
		board[pos] = color;
		BFS(pos); // find libs and worms
		cancelBFS(pos);
		BFSALL();
	}

	// one worm only need BFS once
	static private void cancelBFS(int pos) {
		int next = pos;
		do {
			needReBFS[next] = false;
			next = next_stone[next];
		} while (pos != next);
	}

	static private void BFSALL() {
		for (int i = 0; i < needReBFS.length; ++i) {
			if (needReBFS[i]) {
				cancelBFS(i);
				BFS1(i);
			}
		}
	}

	// libn, libs, next_stone,board
	static private void snapshot(int level) {
		System.arraycopy(board, 0, board_copy[level], 0, MAX_SIZE);
		System.arraycopy(libn, 0, libn_copy[level], 0, MAX_SIZE);
		System.arraycopy(next_stone, 0, next_copy[level], 0, MAX_SIZE);
		for (int i = 0; i < MAX_SIZE; ++i) {
			int n = libn[i];
			for (int j = 0; j < n; ++j) {
				libs_copy[level][i][j] = libs[i][j];
			}
		}
	}

	// libn, libs, next_stone
	static private void recover(int level) {
		System.arraycopy(board_copy[level], 0, board, 0, MAX_SIZE);
		System.arraycopy(libn_copy[level], 0, libn, 0, MAX_SIZE);
		System.arraycopy(next_copy[level], 0, next_stone, 0, MAX_SIZE);
		for (int i = 0; i < MAX_SIZE; ++i) {
			int n = libn_copy[level][i];
			for (int j = 0; j < n; ++j) {
				libs[i][j] = libs_copy[level][i][j];
			}
		}
	}

	/*
	 * static private void undoMove(int pos, int level) { Color color =
	 * board[pos]; Color opp_color = color.complement(); board[pos] =
	 * Color.EMPTY; for (int k = 0; k < 4; ++k) { int ai = dumbBrd.posX(pos) +
	 * deltai[k]; int aj = dumbBrd.posY(pos) + deltaj[k]; int apos =
	 * dumbBrd.makePos(ai, aj); if (dumbBrd.inBoard(dumbBrd.makePos(ai, aj))) {
	 * if (board[apos] == color) BFS(apos); if (board[apos] == opp_color)
	 * BFS1(apos); } } }
	 */
	/*
	 * build libn,libs, next_stone
	 */
	static private void BFS(int pos) {
		Arrays.fill(dfs, 0, MAX_SIZE, false);
		Arrays.fill(dfs_lib, 0, MAX_SIZE, false);
		int beg = 0, end = 1;
		queue[0] = pos;
		dfs[pos] = true;
		while (beg != end) {
			for (int k = 0; k < 4; ++k) {
				int ai = dumbBrd.posX(queue[beg]) + deltai[k];
				int aj = dumbBrd.posY(queue[beg]) + deltaj[k];
				int apos = dumbBrd.makePos(ai, aj);
				if (dumbBrd.inBoard(dumbBrd.makePos(ai, aj))) {
					if (board[pos] == board[apos] && !dfs[apos]) {
						dfs[apos] = true;
						queue[end++] = apos;
						if (end == queue.length)
							end = 0;
					} else if (board[apos] == Color.EMPTY) {
						dfs_lib[apos] = true;
					}
				}
			}
			++beg;
			if (beg == queue.length)
				beg = 0;
		}
		int stones = 0;
		int lib_num = 0;
		for (int k = 0; k < MAX_SIZE; ++k) {
			if (dfs[k])
				queue[stones++] = k; // the stones
			if (dfs_lib[k])
				queue2[lib_num++] = k;
		}
		for (int k = 0; k < stones; ++k) {
			if (k != stones - 1)
				next_stone[queue[k]] = queue[k + 1];
			else
				next_stone[queue[k]] = queue[0];
			libn[queue[k]] = lib_num;
			System.arraycopy(queue2, 0, libs[queue[k]], 0, lib_num);
		}
	}

	/*
	 * build only libn,libs
	 */
	static private void BFS1(int pos) {
		Arrays.fill(dfs_lib, 0, MAX_SIZE, false);
		int next = pos;
		do {
			for (int k = 0; k < 4; ++k) {
				int ai = dumbBrd.posX(next) + deltai[k];
				int aj = dumbBrd.posY(next) + deltaj[k];
				int apos = dumbBrd.makePos(ai, aj);
				if (dumbBrd.inBoard(dumbBrd.makePos(ai, aj))
						&& board[apos] == Color.EMPTY) {
					dfs_lib[apos] = true;
				}
			}
			next = next_stone[next];
		} while (next != pos);
		int lib_num = 0;
		for (int k = 0; k < MAX_SIZE; ++k) {
			if (dfs_lib[k])
				queue2[lib_num++] = k;
		}
		next = pos;
		do {
			libn[next] = lib_num;
			System.arraycopy(queue2, 0, libs[next], 0, lib_num);
			next = next_stone[next];
		} while (next != pos);
	}

	static private void initial(Board brd) {
		board = brd.getBoard();
		// System.arraycopy(Brown.next_stone, 0, next_stone, 0, MAX_SIZE);
		Arrays.fill(next_stone, -1);
		ArrayList<Collection<Worm>> two_worms = new ArrayList<Collection<Worm>>();
		two_worms.add(brd.getWorms(Color.WHITE));
		two_worms.add(brd.getWorms(Color.BLACK));
		int[] originAt = new int[MAX_SIZE];
		for (Collection<Worm> worms : two_worms) {
			for (Worm worm : worms) {
				Integer[] arr = worm.toArray(new Integer[worm.size()]);
				for (int i = 0; i <= arr.length - 2; i++)
					next_stone[arr[i]] = arr[i + 1];
				next_stone[arr[arr.length - 1]] = arr[0];
				for (int i = 0; i < arr.length; i++) {
					originAt[arr[i]] = arr[0];
				}
			}
		}
		for (int i = 0; i < MAX_SIZE; ++i) {
			if (board[i] != Color.EMPTY && originAt[i] == i) {
				BFS1(i); // only libs
			}
		}
	}

	static private void print() {
		int BOARD_LENGTH = 13;
		String letters = "   ";
		for (char c = 'A'; c < 'A' + BOARD_LENGTH; c++)
			if (c >= 'I')
				letters += (char) (c + 1);
			else
				letters += c;
		String res = "";
		res += letters + "\n";
		for (int y = BOARD_LENGTH - 1; y >= 0; y--) {
			res += Lib.fixLenInt(y + 1, 2) + " ";
			for (int x = 0; x < BOARD_LENGTH; x++) {
				int pos = dumbBrd.makePos(x, y);
				if (board[pos] == Color.BLACK)
					res += "O";
				else if (board[pos] == Color.WHITE)
					res += "X";
				else if (board[pos] == Color.EMPTY)
					res += "_";
				else {
					res += "H";
				}
			}
			res += " " + Lib.fixLenInt(y + 1, 2);
			res += "\n";
		}
		res += letters + "\n";
		System.out.println(res);
	}
}
